Context-free Grammar (CFG)

A formal why to describe a class of Formal Languages, or to be more precise, context-free languages.

They have the same relation to push-down automaton that Regular Expressions have to Finte Automaton, i.e., they are a different way to express the same idea.

Structure

A CFG G=(V,T,P,S), where

• V: Variables/Symbols that can be replaced using production rules
• \Sigma: Terminals/Symbols that appear in the final strings (Formal Languages)
• P: Set of production rules
• S: The start symbol

Example

Let L=\{a^n b^n c^m|m,n\in\mathbb{N}_0\} be a language. The context-free grammar G, generating that language is defined as follows:

\begin{align} V &= \{ S, A, C \} \\ \Sigma &= \{a,b,c\} \\ P &= \{ AB \to aAb | \varepsilon, C \to cC | \varepsilon \} \\ S &= AC \\\\ G &= \{V, \Sigma, P, S\} \end{align}